#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// 具体步骤：1. 找到链表中点: 快慢指针
//          2. 递归排序前后两部分链表: 归并排序
//          3. 合并两个有序链表: 合并两个有序链表
class Solution
{
public:
    // 思路：归并排序，找到中点，然后递归排序，再合并
    ListNode *sortList(ListNode *head)
    {
        if (!head || !head->next) // 空链表或只有一个节点
            return head;
        ListNode *slow = head;       // 慢指针
        ListNode *fast = head->next; // 快指针
        // 1. 通过快慢指针找到中点
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2. 切断链表，递归排序
        ListNode *second = slow->next; // 后半部分链表头节点
        slow->next = nullptr;          // 切断链表
        ListNode *first = head;        // 前半部分链表头节点
        first = sortList(first);       // 递归排序前半部分
        second = sortList(second);     // 递归排序后半部分
        // 和并链表
        return mergeList(first, second); //     合并两个有序链表
    }
    ListNode *mergeList(ListNode *first, ListNode *second)
    {
        ListNode *dummy = new ListNode(0);
        ListNode *tail = dummy;
        while (first && second)
        {
            if (first->val > second->val)
            {
                tail->next = second;
                second = second->next;
            }
            else
            {
                tail->next = first;
                first = first->next;
            }
            tail = tail->next;
        }
        if (first)
        {
            tail->next = first;
        }
        if (second)
        {
            tail->next = second;
        }
        return dummy->next;
    }
};